7447. Cut a string

You are given a string s. It is allowed to take any two same neighbor symbols of this string and delete them. This operation you can do while possible. At the beginning you can choose any symbols from string and delete them. Determine the minimum number of symbols you can delete at the beginning, so that you get the empty string after performing allowed operations.

Input. One string s of length no more than 100.

Output. Print the minimum number of symbols you should delete at the beginning.

Sample input	Sample output
abacdeec	2

SOLUTION

dynamic programming

Algorithm analysis

Let dp[l][r] = f(l, r) be the minimum number of characters that should be removed from the substring s_l..s_r, so that later, as a result of applying operations (removing identical adjacent characters), an empty string can be obtained. Then:

· f(l, r) = 0, if l > r;

· f(l, l) = 1, single character should be removed at the beginning;

· f(l, r) = f(l + 1, r – 1), if s[l] = s[r]. If the leftmost and the rightmost characters are the same, then the inner part should be deleted, after which these characters become adjacent and they can be deleted by applying the operation;

· f(l, r) = 1 + f(l + 1, r), if we remove the first character;

· f(l, r) = 1 + f(l, r – 1), if we remove the last character;

However, the last two conditions can be included in the following: to solve the problem on the segment [l; r] let’s solve the problem separately on segments [l; i] and [i + 1; r] (l ≤ i < r) and take the smallest result:

f(l, r) =

For example, the case of removing the first character from the string is equivalent to i = l (then f(l, l) = 1), and the case of removing the last character is equivalent to i = r – 1 (f (r, r) = 1).

The answer to the problem is dp[0][n – 1] = f(0, n – 1), where n is the length of the input string.

Example

Consider the sample given in the problem statement. We have:

f(0, 7) = f(0, 2) + f(3, 7) = 1 + 1 = 2

Algorithm realization

Declare the arrays.

#define MAX 101

#define INF 0x3F3F3F3F

int dp[MAX][MAX];

string s;

Let f(l, r) be the solution of the problem on the segment [l; r].

int f(int l, int r)

{

if (l > r) return 0;

if (l == r) return 1;

if (dp[l][r] != INF) return dp[l][r];

int &res = dp[l][r];

if (s[l] == s[r])

res = min(res, f(l + 1, r - 1));

for (int i = l; i < r; i++)

res = min(res, f(l, i) + f(i + 1, r));

return res;

}

The main part of the program. Read the line.

cin >> s;

memset(dp,0x3F,sizeof(dp));

Compute and print the answer f(0, n – 1), where n is the length of string s.

printf("%d\n",f(0, s.size() - 1));

Java realization

import java.util.*;

public class Main

{

static String s;

static int dp[][];

static int f(int l, int r)

{

if (l > r) return 0;

if (l == r) return 1;

if (dp[l][r] != Integer.MAX_VALUE) return dp[l][r];

int res = dp[l][r];

if (s.charAt(l) == s.charAt(r))

res = Math.min(res, f(l + 1, r - 1));

for (int i = l; i < r; i++)

res = Math.min(res, f(l, i) + f(i + 1, r));

return dp[l][r] = res;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

s = con.nextLine();

int n = s.length();

dp = new int[n][n];

for(int i = 0; i < n; i++)

for(int j = 0; j < n; j++)

dp[i][j] = Integer.MAX_VALUE;

System.out.println(f(0, n - 1));

con.close();

}

}